package com.algorithm.ch1.cjm.dynamic;

/**
 * 求最大子数组的和
 */
public class MaxSubArray {

    public static void main(String[] args) {

        int[] nums = new int[]{-7,-6,-4,5,-1,-10,-100};

        int i = maxSubArray2(nums);
        System.out.println(i);

//        int j = maxSubArray(nums);
//        System.out.println(j);
    }

    /**
     * 动态规划
     * TODO 找时间再看看
     * @param nums
     * @return
     */
    public static int maxSubArray2(int[] nums) {
        // write your code
        int maxEndingHere = nums[0];
        int maxSoFar = nums[0];

        for( int i =1 ;i < nums.length; i++) {
            maxEndingHere = Math.max(nums[i] , nums[i] + maxEndingHere );
            maxSoFar = Math.max( maxSoFar, maxEndingHere);
        }
        return maxSoFar;

    }

    /**
     * 时间复杂度 O(n)
     * @param nums
     * @return
     */
    public static int maxSubArray1(int[] nums) {
        // write your code
        int maxsum = Integer.MIN_VALUE;
        int sum = 0;
        for(int i = 0;i<nums.length;i++){
            if ( sum < 0 ){
                sum = 0;
            }
            sum += nums[i];
            maxsum = Math.max(maxsum, sum);

        }
        return maxsum;
    }

    /**
     * 时间复杂度O(n2)
     * @param gap
     * @return
     */
    public static int maxSubArray(int[] gap){

        int max = Integer.MIN_VALUE;
        for (int i = 0; i < gap.length; i++) {

            int sum = 0;
            for(int j = i; j < gap.length; j++){

                sum += gap[j];
                max = Math.max(sum, max);
            }

        }

        return max;
    }

}
